{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 决策树简介"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "决策树算是最好理解的分类器了。\n",
    "\n",
    "**决策树就是一个多层if-else函数，就是对对象属性进行多层if-else判断，获取目标属性（类标签）的类别。**\n",
    "\n",
    "由于只使用if-else对特征属性进行判断，所以一般特征属性为离散值，即使为连续值也会先进行区间离散化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/ef8a68022452fb03159a7a805dd88041.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在机器学习中，决策树是一个预测模型，他代表的是对象属性与类别属性之间的一种映射关系。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分类决策树概念：**是一种描述对实例进行分类的树形结构。**\n",
    "\n",
    "决策树由结点和有向边组成。结点有两种类型：**内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个分类。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 思考：选哪些特征属性参与决策树建模、哪些属性排在决策树的顶部，哪些排在底部，对属性的值该进行什么样的判断、样本属性的值缺失怎么办、\n",
    "\n",
    ">如果输出不是分类而是数值能用么、对决策没有用或没有多大帮助的属性怎么办、什么时候使用决策树？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**使用决策树做预测需要以下过程：**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1、收集数据：可以使用任何方法。比如想构建一个相亲系统，我们可以从媒婆那里，或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。\n",
    "\n",
    "2、准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。\n",
    "\n",
    "3、分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。\n",
    "\n",
    "4、训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一个决策树的数据结构。\n",
    "\n",
    "5、测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 信息增益\n",
    "\n",
    "信息增益表示**得知特征$X^j$的信息而使所属分类的不确定性减少的程度。**\n",
    "\n",
    "特征$A$对训练数据集$D$的信息增益$g(D,A)$，定义为集合$D$的经验熵$H(D)$与特征A给定的情况下D的经验条件熵$H(D|A)$之差。\n",
    "$$g(D,A) =H(D) - H(D|A) $$\n",
    "假设数据集D有K种分类，特征A有n种取值可能。\n",
    "\n",
    "其中数据集D的经验熵$H(D)$为\n",
    "\n",
    "$$H(D)=-\\sum_{k=1}^K P_klog_2^{P_k}$$  其中$P_k$为集合D中的任一样本数据分类k的概率，或者说属于分类k的样本所占的比例。\n",
    "\n",
    "经验条件熵$H(D|A)$为\n",
    "\n",
    "$$H(D|A)=\\sum_{i=1}^n P_i H(D_i)$$  其中$P_i$为特征取值为第i个可取值的概率。$D_i$为特征A为第i个可取值的样本集合。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 信息增益比\n",
    "\n",
    "特征$A$对训练数据集$D$的信息增益$g_R(D,A)$，定义为其信息增益$g(D,A)$与训练集D的经验熵$H(D)$之比。\n",
    "\n",
    "$$g_R(D,A) = g(D,A) / H(D)$$\n",
    "\n",
    "是为了矫正在训练数据集的经验熵大时，信息增益值会偏大，反之，信息增益值会偏小的问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 决策树ID3算法的思路\n",
    "\n",
    "\n",
    "ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**不足：**\n",
    "\n",
    "ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。　　\n",
    "\n",
    "**a)**ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。\n",
    "\n",
    "**b)**ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？\n",
    "\n",
    "**c)** ID3算法对于缺失值的情况没有做考虑\n",
    "\n",
    "**d)** 没有考虑过拟合的问题\n",
    "\n",
    "ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是下一节要说的C4.5算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
